package priv.conceit.study.leetcode.medium;

import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

/**
 * 编号208
 * 实现 Trie (前缀树)
 * <a href="https://leetcode-cn.com/problems/implement-trie-prefix-tree/comments/"></a>
 * 实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。
 *
 * 示例:
 * Trie trie = new Trie();
 *
 * trie.insert("apple");
 * trie.search("apple");   // 返回 true
 * trie.search("app");     // 返回 false
 * trie.startsWith("app"); // 返回 true
 * trie.insert("app");
 * trie.search("app");     // 返回 true
 *
 * 说明:
 * 你可以假设所有的输入都是由小写字母 a-z 构成的。
 * 保证所有输入均为非空字符串。
 *
 * @author conceit
 * @since 1.0.0, 2019/7/3
 */
@SuppressWarnings("all")
public class ImplementTriePrefixTree {



	/**
	 * 小写字母 a-z共26位
	 */
	public static int dictSize=26;
	public TrieNode root;

	/**
	 * 初始化时 便捎带初始化一个空的node
	 */
	public ImplementTriePrefixTree() {
		root=new TrieNode(' ');
	}


	/**
	 * 新增
	 * 每个子目录下一行的arr[]位26
	 * 用arr[diff]就可以获取到指定node上是否包含字符
	 *
	 * 从root节点开始执行 如找到指定字符 则将root指向子节点
	 * @param word
	 */
	public void insert(String word) {

		TrieNode curNode=root;
		for (int i=0;i<word.length();i++){
			int diff=word.charAt(i)-'a';
			if(curNode.childs[diff]==null){
				curNode.childs[diff]=new TrieNode(word.charAt(i));
			}
			curNode=curNode.childs[diff];
		}
		curNode.isLast=Boolean.TRUE;

	}

	/**
	 * input必须和trie全匹配
	 *
	 * @param word
	 * @return
	 */
	public boolean search(String word) {
		TrieNode curNode=root;
		for(int i=0;i<word.length();i++){
			int diff=word.charAt(i)-'a';
			if(curNode.childs[diff]==null){
				return false;
			}
			curNode=curNode.childs[diff];
		}
		return curNode.isLast;
	}


	/**
	 * 查询前缀
	 * @param prefix
	 * @return
	 */
	public boolean startsWith(String prefix) {
		TrieNode curNode=root;
		for(int i=0;i<prefix.length();i++){
			int diff=prefix.charAt(i)-'a';
			if(curNode.childs[diff]==null){
				return false;
			}
			curNode=curNode.childs[diff];
		}
		return true;
	}

	/**
	 * 查询该前缀树结构每一个层级
	 *
	 * 如果第一个层级为空则直接返回
	 *
	 * 不为空则检查该目录是否只包含一个节点且不为空
	 *
	 * 不为空且只有一个节点 则检查该节点是否为最终节点
	 *
	 * 是则为公共前缀
	 * 不是则继续向下遍历
	 * 依次循环
	 *
	 * 如果只有一个字符则直接返回""
	 *
	 * @return String
	 */
	public String searchLongestCommonPrefix(){
		String result = "";
		TrieNode curNode = root;
		while (true) {

			if (curNode.childs == null) {
				break;
			}
			List<TrieNode> trieNodeList = Arrays.asList(curNode.childs).stream().filter(x -> x != null).collect(Collectors.toList());
			if (trieNodeList.size() > 1||trieNodeList.size()==0) {
				break;
			} else {
				curNode = trieNodeList.stream().findFirst().get();
				if (curNode.isLast) {
					return result + curNode.value;
				} else {
					result = result + curNode.value;
				}
			}
		}

		return result;
	}

	/**
	 * TrieNode为节点
	 */
	private class TrieNode{
		/**
		 * 初始化方法
		 * @param value
		 */
		public TrieNode(char value) {
			this(new TrieNode[ImplementTriePrefixTree.dictSize],value,Boolean.FALSE);
		}

		public TrieNode(TrieNode[] childs,char value,boolean isLast){
			this.childs=childs;
			this.isLast=isLast;
			this.value=value;
		}

		/**
		 * 下属的子孙节点
		 */
		private TrieNode[] childs;
		/**
		 * 是否为最后一个节点
		 */
		private boolean isLast;
		/**
		 * 当前的字符
		 */
		private char value;



	}




	public static void main(String[] args) {

		ImplementTriePrefixTree trie=new ImplementTriePrefixTree();
		trie.insert("wocaonima");

		System.out.println("wocao search-->"+trie.search("wocao"));
		System.out.println("wocaonim search-->"+trie.search("wocaonim"));
		System.out.println("wocaonima search-->"+trie.search("wocaonima"));
		System.out.println("socaonima search-->"+trie.search("socaonima"));
		System.out.println("nima search-->"+trie.search("nima"));
		System.out.println("mabi search-->"+trie.search("mabi"));

		System.out.println("socaonima startsWith-->"+trie.startsWith("socaonima"));
		System.out.println("wocaonim startsWith-->"+trie.startsWith("wocaonim"));
		System.out.println("w startsWith-->"+trie.startsWith("w"));
		System.out.println("wocao startsWith-->"+trie.startsWith("wocao"));
		System.out.println("nima startsWith-->"+trie.startsWith("nima"));


		//java char 为Unicode 编码
		//Unicode 有 2个字节  ，还有一个扩展的4字节 字符集
		//它的前128字节编码与ASCII兼容，所以‘A’和 'a'的值可以在ASCII码表中查到。
//		String str="abcdefg我日";
//		Character character=new Character('靠');
//
//		System.out.println(character);
//		System.out.println(character.charValue());
//		for(int i=0;i<str.length();i++){
//			System.out.println(str.charAt(i));
//			System.out.println(str.charAt(i)-'a');
//		}
//		//~
//		//0-127 ascii 共128位
//		System.out.println((char)126);
	}


}
